# 二分答案的题目里，一般会出现 最多，最少等字眼

# 检查当前边长 x 是否能切出至少 k 块巧克力
def chk(x):
    total = 0
    for h, w in zip(H, W):
        total += (h // x) * (w // x)
    # 如果 total的值 大于 目标值 说明 x分小了
    return total >= k

# 读取输入
n, k = map(int, input().split())
H = []
W = []
for _ in range(n):
    h, w = map(int, input().split())
    H.append(h)
    W.append(w)

# 二分查找最大边长
# 原区间是 1  min(max(H), max(W))
# 我们需要的是 左右开区间 所以 原区间的left-1 right+1
# 定义开区间 是因为 我们的left，right不进行+1，-1 处理，直接赋值mid 同时，不会使 二分完后 left 的值 大于 right的值,保证 left 是永远小于 right的
left, right = 0, min(max(H), max(W))+1
while left+1 < right:
    mid = (left + right) // 2
    if chk(mid):
        # x 分小了， 提升 l 的值
        left = mid
    else:
        # x分大了，减少 r 的值
        right = mid

# 从最小的里面 找出 最大的
# 在一个升序 序列里面 找到一个满足条件里面的 最大值  0 left right ...  left 和 right是分界线,
# left 的左边是 满足条件的  right 的右边是 不满足条件的
print(left)
